/*
 * comparison.cpp
 *
 *  Created on: May 23, 2011
 *      Author: Manslaughter
 */

#include "BigInt.h"
#include <stdio.h>
using namespace APIAL;

/*
	TODO: Implement a single comparison function that returns:
		-1 if left < right
		0 if left == right
		1 if left > right
	Thus, <, >, <=, >=, ==, and != can be implemented as a simple run of
	this comparison function and a test of the result (i.e. <= if comparison <= 0)
*/

bool APIAL::Equal(BigInt *left, BigInt *right) {
	// Check for Aliasing 
	if(left == right)
		return true;

	// Check sign
	if (left->positive != right->positive)
		return false;

    // Guarantee normalization on all bitwise ops
    BigInt::normalize(*left);
    BigInt::normalize(*right);

    // Handle the easy cases
    if(left->size != right->size)
        return false;

	// TODO: break out early from this loop if non-equal

	// Bitwise or (|) reduction, will be non-zero if any bits differ
	BigInt::chunkType result = 0;
	#pragma omp parallel for reduction(|:result) shared(left, right)
	for(int i = 0; i < left->size; i++) {
		// Chunks are normalized, do a straight comparison
		result = result | ((left->chunks[i]) ^ (right->chunks[i]));
	}

	// Equal if result is zero
	return result == 0;
}

// TODO: can parallelize this similar to equality checking
bool BigInt::operator<(BigInt& bi) {
	// If alias, punish caller by checking
	// In normal case, reward user by not performing additional check
	if (this->positive && !bi.positive)
		return false;
	else if (!this->positive && bi.positive)
		return true;

	// Normalize before comparison
	BigInt::normalize(*this);
	BigInt::normalize(bi);

	// Compare size
	if (this->size < bi.size) {
		return this->positive;
	} else if (this->size > bi.size) {
		return !this->positive;
	}

	// Compare the rest of the chunks
	for (int i = this->size-1; i >= 0; i--) {
		if (this->chunks[i] < bi.chunks[i])
			return this->positive;
		else if (this->chunks[i] > bi.chunks[i])
			return !this->positive;
	}

	// Equal
	return false;
}

// TODO: can parallelize this similar to equality checking
bool BigInt::operator>(BigInt& bi) {
	// If alias, punish caller by checking
	// In normal case, reward user by not performing additional check

	// Compare sign
	if (this->positive && !bi.positive)
		return true;
	else if (!this->positive && bi.positive)
		return false;

	// Normalize before comparison
	BigInt::normalize(*this);
	BigInt::normalize(bi);

	// Compare size
	if (this->size > bi.size) {
		return this->positive;
	} else if (this->size < bi.size) {
		return !this->positive;
	}

	// Compare the rest of the chunks
	for (int i = this->size-1; i >= 0; i--) {
		if (this->chunks[i] > bi.chunks[i])
			return this->positive;
		else if (this->chunks[i] < bi.chunks[i])
			return !this->positive;
	}
	
	// Equal
	return false;
}

//	return if left < right
//  leftchunk is most significant chunk to look at (index)
//  rightchunk is the most significant chunk to look at (index)
//  leftbit is the most significant bit within leftchunk to begin (index)
//  rightbit is the most significant bit within rightchunk to begin (index)
//  leftlength is total number of bits to compare
//  rightlength is total number of bits to compare

bool BigInt::isLessThan(BigInt *left,  int leftChunk,  int leftBit,  int leftLength,
	BigInt *right, int rightChunk, int rightBit, int rightLength) {

	#pragma omp parallel sections
	{
		// get rid of leading zeros on left side
		while (leftLength > 0) {
			if ((left->chunks[leftChunk] & (1 << leftBit)) == 0) {
				leftLength--;
				leftBit--;
				if (leftBit < 0) {
					leftChunk--;
					leftBit = left->nonCarryBits;
				}
			}
			else
				break;
		}

		// get rid of leading zeros on left side
		#pragma omp section
		while (rightLength > 0) {
			if ((right->chunks[rightChunk] & (1 << rightBit)) == 0) {
				rightLength--;
				rightBit--;
				if (rightBit < 0) {
					rightChunk--;
					rightBit = right->nonCarryBits;
				}
			}
			else
				break;
		}
	}

	// check to see if lengths are different (easy compare if they are)
	if (leftLength < rightLength)
		return true;
	else if (rightLength < leftLength)
		return false;

	// begin comparing
	while (leftLength > 0) {

		// get the bit and push it to the lsb
		int leftTmp = (left->chunks[leftChunk] >> leftBit) & 1;
		int rightTmp = (right->chunks[rightChunk] >> rightBit) & 1;

		// compare
		if (leftTmp < rightTmp)
			return true;
		else if (rightTmp < leftTmp)
			return false;

		// decrement
		leftLength--;
		leftBit--;
		rightBit--;
		if (leftBit < 0)
		{
			leftChunk--;
			leftBit = left->nonCarryBits;
		}
		if (rightBit < 0)
		{
			rightChunk--;
			rightBit = right->nonCarryBits;
		}
	}

	// if everything matches up then they're equal
	return false;
}
